The present invention relates to a method of asynchronous circuit synthesis which results in the design of an initializable circuit whether or not the initial design specification is functionally initializable. When the initial design specification is not functionally initializable, the specification is modified to result in a functionally initializable design without changing the operating characteristics of the design.
Initializability is a key requirement for ensuring the testability of sequential circuits. However, state-of-the-art automatic tools for synthesizing asynchronous circuits may result in circuits that are not initializable by gate level analysis tools.
The rapidly increasing complexity of today's systems and the critical demand for high performance has led designers to reconsider asynchronous design methodology. A synchronous circuit may be viewed as a restricted version of an asynchronous circuit where all operations are performed in synchrony with a global clock. The discreteness of time by the global clock facilitates analysis, synthesis, and testing. However, a global clock presents other problems such as clock skew, high power consumption, and worst case execution time that confine high performance applications to small chip areas. Asynchronous designs typically provide a better performance than comparable synchronous designs in situations where global synchronization with a high-speed clock limits system throughput. Elimination of global synchronization is perhaps the greatest motivating force behind the asynchronous approach. For computations that are data dependent, asynchronous specifications are more natural. Operations are performed upon the availability of operands and there is no need to wait for the arrival of a global synchronization signal. However, until recently these advantages had been overlooked due to the inherent complexities associated with the feasible implementation and testing of asynchronous designs.
Significant advances have been made in automating the synthesis of asynchronous circuits. These techniques have been embodied in several computer-aided design tools such as are described in a PhD thesis entitled "Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications" by T. A. Chu at MIT in 1987 and in a PhD thesis entitled "Synthesis and Testing of Bounded Wire Delay Asynchronous Circuits from Signal Transition Graphs," by L. Lavagno at UC Berkeley in 1992. However, significant difficulty has been experienced in testing the circuits that were synthesized by these automatic programs. Some of the circuits could not be initialized by the test generator and therefore, no test sequence was generated. Initialization is the process of driving the state signals in the circuit to a known state irrespective of the power-up state of the circuit. This is an important first phase in the test generation of sequential circuits. In the absence of designer-supplied initialization vectors for automatically synthesized circuits, the test generator has to derive the initialization sequence. All state signals in the circuit are initially assumed to be in an unknown state and the test generator derives a sequence of input vectors that will bring all state signals to a known state. If the synthesized implementation cannot be initialized, then the test generator or other gate level analysis tools are completely ineffective.
The difficulty in testing the synthesized implementations can be understood by looking at the current focus of asynchronous circuit synthesis tools. Since the synthesis problem is so difficult, previous work on automatic synthesis was primarily aimed at solving the basic issues. It focused on realizing minimum logic and hazard-free implementations. These two objectives do not guarantee that the implementation is initializable. In fact, minimal area implementations may have to be sacrificed for initializable implementations.
Initializability of synchronous sequential circuits has been described in an article by C. Pixley and G. Beihle entitled "Calculating Resetability and Reset Sequences", Proc. of the Int. Conf. on Computer Aided Design, pp. 376-379, 1992 and in an article by C. Pixley, S. W. Jeong and G. D. Hatchel entitled "Exact Calculation of Synchronization Sequences Based on Binary Decision Diagrams", Proc. of the 29th ACM/ICEE Design Automation Conf., pp. 620 to 623, 1992. These methods determine whether or not a given circuit is initializable and determine the initialization sequences for the initializable circuits. The initialization problem is also manifest in the automatic synthesis of synchronous circuits where the improper state assignment results in implementations that are not initializable. Mathew and Saab in an article entitled "Partial Reset: An Inexpensive Design for Testability Approach" in Proc. EDAC/EURO-ASIC, pp 151 to 155, April 1993, identified the importance of initializability and provided a low-cost solution by providing a technique to perform partial reset in the hardware.
Explicit reset mechanism is a post-synthesis modification that requires an extra primary input and some additional logic for each state signal. Also, the wiring from the reset input pin to the state signals is an additional overhead. A more attractive solution is to consider circuit testability during the synthesis procedure itself and realize initializable implementations without explicit reset.
A design is functionally initializable if there exists at least one corresponding gate-level implementation that is initializable. Circuit initializability is intimately related to the don't care assignments made during synthesis. However, this procedure fails when the specification of the asynchronous circuit is functionally uninitializable.